package xyf.p04.tree;

import commons.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * ClassName: J034_SumPath
 * Description:
 * Author: xyf
 * Date: 9/8/22 6:10 PM
 * Version: 1.0
 **/
public class J034_SumPath
{
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target)
    {
        if (root == null)
        {
            return res;
        }
        dfs(root, 0, target, new LinkedList<>());
        return res;
    }

    private void dfs(TreeNode root, int currentSum, int target, LinkedList<Integer> sum)
    {
        currentSum += root.val;
        sum.addLast(root.val);

        if (root.left == null && root.right == null)
        {
            if (currentSum == target)
            {
                List<Integer> snapShot = new LinkedList<>();
                snapShot.addAll(sum);
                res.add(snapShot);
            }
            sum.removeLast();
            return;
        }

        if (root.left != null)
        {
            dfs(root.left, currentSum, target, sum);
        }

        if (root.right != null)
        {
            dfs(root.right, currentSum, target, sum);
        }

        sum.removeLast();
    }
}